#ifndef __HASHMAP_H_
#define __HASHMAP_H_
#include<iostream>
#include<string>
template<typename T>
class HashMap//键值对
{
public:
    HashMap(const int &size);
    void Insert(const std::string &key,const T & value);
    void Remove(const std::string &key);
    T* GetByKey(const std::string key);
    T& operator[](const std::string& key);
    template<typename U>
    friend  std::ostream& operator<<(std::ostream&os,const HashMap<U>& map);
    


private:
    struct Node //结点
    {
    Node(const std::string key,const T &value):key(key),value(value),next(nullptr){}
    std::string key;//键
    T value;//值
    Node *next;//指向下一个节点的指针
    };
    Node* *array;//数组指针
    const int size;//数组大小
    //哈希函数
    int Hash(const std::string& key);
};
template<typename T>
std::ostream& operator<<(std::ostream&os,const HashMap<T>& map)
{
        for(int i=0;i<map.size;i++)
    {
    typename HashMap<T>::Node* travePoint=map.array[i];
     //链表的遍历
     while(travePoint!=nullptr)
    {
        std::cout<<"哈希值："<<i<<" "
        <<"key:"<<travePoint->key<<" "
        <<"value:"<<travePoint->value<<" ";
        std::cout<<std::endl;
        travePoint=travePoint->next;
    }
    }
    return os;
}
template<typename T>
HashMap<T>::HashMap(const int &size):size(size)
{
    array=new Node*[size];
    for(int i=0;i<size;i++)
    {
        array[i]=nullptr;
    }
}
template<typename T>
void HashMap<T>::Insert(const std::string &key, const T &value)
{
    Node *node=new Node(key,value);
    //计算哈希值
    int index=Hash(key);
    //头插
    node->next= array[index];
    array[index]=node;
}
template<typename T>
void HashMap<T>::Remove(const std::string &key)
{
    Node *node=array[Hash(key)];
    if(node==nullptr)
        return;
    if(node->key==key)
    {
        array[Hash(key)]=node->next;
        delete node;
        return;
    }
    else
    {
        Node* travePoint=node;
        while(travePoint->next!=nullptr)
        {
            if(travePoint->next->key==key)
            {
                Node *freeNode=travePoint->next;
                travePoint->next=freeNode->next;
                delete freeNode;
                return;
            }
            travePoint=travePoint->next;

        }
    }
}
template<typename T>
T *HashMap<T>::GetByKey(const std::string key)
{
    Node *node=array[Hash(key)]; //O(1)
    while(node!=nullptr)//O(n),链表越长效率越低
    {
        if(node->key==key)
        {
            return &node->value;
        }
        node=node->next;
    }
    return nullptr;
   
}
template<typename T>
 T &HashMap<T>::operator[](const std::string &key)
{
   T *data=GetByKey(key);
    //存在就返回
    if(data)
        return *data;
    //不存在就创建
    else
    {
        Insert(key,T());//匿名对象
        return *GetByKey(key);
    }
}


template<typename T>
int HashMap<T>::Hash(const std::string &key)
{
    int hash=0;
    for(int i=0;i<key.size();i++)
    {
        hash=(hash*31+key[i])%size;//引入素数将字符串每位值加起来取余
    }
    return hash;
}

#endif
